class Solution {
    public int largestRectangleArea(int[] heights) {
        /**
        栈里面一直是升序的（栈里面放的是下标）
        2,1,5,6,4,3
        栈（-1,0（2））   1（1）当到达他时，栈顶比他大，弹出area=2*（1-（-1）-1）=2
        栈（-1,1（1），2（5），3（6）） 4（4）到达时，弹出area=（4-2-1）*6=6  
                    area=（4-1-1）*5=10
        栈（-1,1（1），4（4））  5（3）到达时，area=（5-1-1）*4=12
        栈（-1,1（1），5（3）） 完了之后遍历栈 5（3）-->（6-1-1）*3=12
                            1（1）-->（6-（-1）-1）*1=6
         */
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int area = 0;
        for (int i = 0, length = heights.length; i < length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                area = Math.max(area, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            area = Math.max(area, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return area;
    }

    private int aa(int[] heights) {//该方法用例通过，但是超出时间限制
    //遍历数组，在每一个下标开始左右移动，找到比他大（或等于）的块，计算
        int length = heights.length;
        if(length == 0) {
            return 0;
        }
        if(length == 1) {
            return heights[0];
        }
        int mianji = 0;
        for (int i = 0; i < length; i++) {
            int left = i;
            int rigth = i;
            while (left >= 0 || rigth <= (length -1)) {
                if(left > 0 && (heights[i] <= heights[left - 1])) {
                    if(heights[i] <= heights[left - 1]) {
                        left--;
                    }
                    continue;
                }
                if(rigth < (length - 1) && (heights[i] <= heights[rigth + 1])) {
                    if(heights[i] <= heights[rigth + 1]) {
                        rigth++;
                    }
                    continue;
                }
                break;
            }
            int daxiao = (rigth - left + 1) * heights[i];
            mianji = Math.max(mianji,daxiao);
        }
        return mianji;
    }
}